class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}



public class project {
    public int lastStoneWeightII(int[] stones) {
        int len=stones.length;
        int sum=0;
        for(int stone:stones){
            sum+=stone;
        }
        int mid=sum/2;
        int[] dp=new int[mid+1];
        for(int i=0;i<len;i++){
            for(int j=mid;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[mid]-dp[mid];
    }















    public int numberOfArithmeticSlices(int[] nums) {
        int len=nums.length;
        if(len<3){
            return 0;
        }
        int mid=nums[0]-nums[1];
        int ret=0;
        int count=0;
        for(int i=2;i<len;i++){
            if(nums[i-1]-nums[i]==mid){
                count++;
            }else{
                mid=nums[i-1]-nums[i];
                count=0;
            }
            ret+=count;
        }
        return ret;
    }











    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int[] start={0,0};
        int abs=manhattan(start,target);
        for(int[] ghost:ghosts){
            int tmp=manhattan(ghost,target);
            if(tmp<=abs){
                return false;
            }
        }
        return true;
    }
    public int manhattan(int[] start,int[] target){
        return Math.abs(start[0]-target[0])+Math.abs(start[1]-target[1]);
    }














    int ret=Integer.MIN_VALUE;
    public int maxAncestorDiff(TreeNode root) {
        dfs(root,root.val,root.val);
        return ret;
    }
    public void dfs(TreeNode root,int max,int min){
        if(root==null){
            return;
        }
        max=Math.max(max,root.val);
        min=Math.min(min,root.val);
        if(root.left==null&&root.right==null){
            ret=Math.max(ret,Math.abs(max-min));
        }
        dfs(root.left,max,min);
        dfs(root.right,max,min);
    }
















    public boolean validUtf8(int[] data) {
        int n=data.length;
        for(int i=0;i<n;){
            int tmp=data[i];
            int j=7;
            while (j>=0&&(((tmp>>j)&1)==1)){
                j--;
            }
            int count=7-j;
            if(count==1||count>4){
                return false;
            }
            if(i+count-1>=n){
                return false;
            }
            for(int k=i+1;k<i+count;k++){
                if((((data[k]>>7)&1)==1)&&(((data[k]>>6)&1)==0)){
                    continue;
                }
                return false;
            }
            if(count==0){
                i++;
            }else{
                i+=count;
            }
        }
        return true;
    }
}
